/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */


#ifndef __PACKED_VALUE_SET_TEST_HPP__
#define __PACKED_VALUE_SET_TEST_HPP__

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/portability/Stream.h>

#include <cubefs/core/tools/packed_map.hpp>

using namespace std;

namespace cubefs {
namespace core {
namespace tests {
namespace packed_map_ns {

template<typename Constants>
class PackedValueSetTest : public CPPUNIT_NS::TestFixture
{
    CPPUNIT_TEST_SUITE(PackedValueSetTest);


    CPPUNIT_TEST(testCreateIndex);
    CPPUNIT_TEST(testFind);

    CPPUNIT_TEST_SUITE_END();


    char buffer[4096];

protected:

    typedef packed_value_map<long, void_value, Constants> Map;

    Map map;

    typedef typename Map::index_t index_t;
    typedef typename Map::key_t key_t;

public:

    PackedValueSetTest() {}

    void setUp() {
        for (unsigned c = 0; c < sizeof(buffer); c++) {
            buffer[c] = 0;
        }

        for (index_t c = 0; c < map.max_size(); c++) {
            map.add(c*2);
        }

        map.reindex();
    }

    void tearDown() {}

    void testCreateIndex() {
        CPPUNIT_ASSERT_EQUAL((index_t)map.max_size(), (index_t)map.size());

        index_t nlevels = map.get_index_levels_count();
        index_t base = 1;
        for (index_t l = 1; l < nlevels; l++) {
            key_t last = 0;
            index_t size = map.get_elements_on_level(l);

            for (index_t i = 0; i < size; i++) {
                key_t key = map.index(i + base);
                CPPUNIT_ASSERT(key > last);
                last = key;
            }

            base += size;
        }
    }

    void testFind() {
        for (key_t c = 0; c < map.size() - 1; c++) {
            index_t idx = map.find_le(c * 2);
            CPPUNIT_ASSERT_EQUAL(idx, c);

            idx = map.find_le(c * 2 + 1);
            CPPUNIT_ASSERT_EQUAL(idx, c + 1);

            idx = map.find_eq(c * 2);
            CPPUNIT_ASSERT_EQUAL(idx, c);

            idx = map.find_eq(c * 2 + 1);
            CPPUNIT_ASSERT_EQUAL(idx, (key_t)-1);

            idx = map.find_lt(c * 2); //?????????????????????????
            CPPUNIT_ASSERT_EQUAL(idx, c + 1);

            idx = map.find_lt(c * 2 - 1);
            CPPUNIT_ASSERT_EQUAL(idx, c);
        }

        //find lower bound
        index_t idx = map.find_le(-1);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)0);

        idx = map.find_eq(-1);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)-1);

        idx = map.find_lt(-1);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)0);


        //find upper bound
        key_t upper = map.max_key();
        idx = map.find_le(upper + 1);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)-1);

        idx = map.find_le(upper);
        CPPUNIT_ASSERT_EQUAL(idx, (index_t)map.size() - 1);

        idx = map.find_eq(upper + 1);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)-1);

        idx = map.find_eq(upper);
        CPPUNIT_ASSERT_EQUAL(idx, (index_t)map.size() - 1);

        idx = map.find_lt(upper);
        CPPUNIT_ASSERT_EQUAL(idx, (key_t)-1);

        idx = map.find_lt(upper - 1);
        CPPUNIT_ASSERT_EQUAL(idx, (index_t)map.size() - 1);
    }
};

} //packed_map_ns
} //tests
} //core
} //cubefs

#endif
